﻿namespace DLLPrime
{
    public class Prime
    {
        List<int> a;  // 用于保存生成的质数列表
        int maxNum = 0;

        // 构造函数，使用埃拉托色尼筛法生成质数，n 为质数筛选的上限
        public Prime(int n)
        {
            maxNum = n;
            a = SieveOfEratosthenes(n);
        }
        public Prime() : this(1000) { }
        // 使用埃拉托色尼筛法生成质数
        private List<int> SieveOfEratosthenes(int n)
        {
            List<int> primes = new List<int>();
            bool[] isPrime = new bool[n + 1];

            // 初始化所有数字都标记为质数
            for (int i = 2; i <= n; i++)
            {
                isPrime[i] = true;
            }
            // 埃拉托色尼筛法
            for (int i = 2; i * i <= n; i++)
            {
                if (isPrime[i])
                {
                    for (int j = i * i; j <= n; j += i)
                    {
                        isPrime[j] = false;
                    }
                }
            }
            // 将所有标记为质数的数字添加到质数列表中
            for (int i = 2; i <= n; i++)
            {
                if (isPrime[i])
                {
                    primes.Add(i);
                }
            }
            return primes;
        }
        // 判断一个数是否为质数
        public bool isPrime(int i)
        {
            if (i < 2) return false;
            foreach (int prime in a)
            {
                if (prime * prime > i) break;  // 优化，避免不必要的计算
                if (i % prime == 0) return false;
            }
            return true;
        }
        public string PrimeFactors(int x)
        {
            string result = "";
            if (x <= 2 || x>maxNum) { throw new Exception($"错误，PrimeFactors方法参数应该介于2到{a.Count}之间，x:{x}"); }
            else
            {
                while (! isPrime(x))
                {
                    foreach (int i in a)
                    {
                        if (x%i==0)
                        {
                            result += result == "" ? $"{i}" : $"×{i}";
                            x /= i;
                            break; 
                        }

                    }
                }
                // 只输出质数x
                result += result == "" ? $"1×{x}" : $"×{x}";

            }
            return result;
        }
        // 生成小于等于 max 的质数列表
        // 生成质数列表（返回质数直到 max）
        public List<int> GeneratePrimes(int max)
        {
            return new List<int>(a.FindAll(p => p <= max));
        }
    }
}
